{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Reverse String"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #two-pointers #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #双指针 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: reverseString"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #反转字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 <code>s</code> 的形式给出。</p>\n",
    "\n",
    "<p>不要给另外的数组分配额外的空间，你必须<strong><a href=\"https://baike.baidu.com/item/原地算法\" target=\"_blank\">原地</a>修改输入数组</strong>、使用 O(1) 的额外空间解决这一问题。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = [\"h\",\"e\",\"l\",\"l\",\"o\"]\n",
    "<strong>输出：</strong>[\"o\",\"l\",\"l\",\"e\",\"h\"]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = [\"H\",\"a\",\"n\",\"n\",\"a\",\"h\"]\n",
    "<strong>输出：</strong>[\"h\",\"a\",\"n\",\"n\",\"a\",\"H\"]</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>s[i]</code> 都是 <a href=\"https://baike.baidu.com/item/ASCII\" target=\"_blank\">ASCII</a> 码表中的可打印字符</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [reverse-string](https://leetcode.cn/problems/reverse-string/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [reverse-string](https://leetcode.cn/problems/reverse-string/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[\"h\",\"e\",\"l\",\"l\",\"o\"]', '[\"H\",\"a\",\"n\",\"n\",\"a\",\"h\"]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseString(self, s: List[str]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify s in-place instead.\n",
    "        \"\"\"\n",
    "        def helper(left, right):\n",
    "            if left < right:\n",
    "                s[left], s[right] = s[right], s[left]\n",
    "                helper(left+1, right-1)\n",
    "\n",
    "        helper(0, len(s) - 1)\n",
    "                                            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseString(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        return s[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseString(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        sT=\"\"\n",
    "        ls=len(s)\n",
    "        for i in range(ls):\n",
    "            sT+=s[ls-i-1]\n",
    "        return sT"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseString(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        s = list(s)\n",
    "        i=0\n",
    "        j=len(s)-1\n",
    "        while i<j:\n",
    "            s[i],s[j] = s[j],s[i]\n",
    "            i+=1\n",
    "            j-=1\n",
    "        return ''.join(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseString(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        return s[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseString(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        return s[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseString(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        rev_s = list(s)\n",
    "        return ''.join(rev_s[::-1])\n",
    "    \n",
    "    def reverseString2(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        rev_s = list(s)\n",
    "        return ''.join(rev_s[::-1])\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseString(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        t = list(s)\n",
    "        print()\n",
    "        return \"\".join(t[::-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseString(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        return ''.join([s[i] for i in range(len(s)-1, -1, -1)])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseString(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        i,j,r = 0,len(s) - 1,[[],[]]\n",
    "        m = j >> 1 if len(s) % 2 else None\n",
    "        while i < j:\n",
    "            r[1].insert(0, s[i])\n",
    "            r[0].append(s[j])\n",
    "            i+=1\n",
    "            j-=1\n",
    "        return ''.join(r[0] + [s[m]] + r[1] if m != None else r[0] + r[1])\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseString(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        if \",\" in s:\n",
    "            return \",\".join([i[::-1] for i in s.split(\",\")][::-1])\n",
    "        else:\n",
    "            return \"\".join(s[::-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseString(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        result = []\n",
    "        for i in s:\n",
    "            result.append(i)\n",
    "        result = reversed(result)\n",
    "        return ''.join(result)\n",
    "\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    s = Solution()\n",
    "    print(s.reverseString(\"\"))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseString(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        l = list(s)\n",
    "        print(l)\n",
    "        l.reverse()\n",
    "        print(l)\n",
    "        s=\"\".join(l)\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseString(self, s):\n",
    "        \"\"\"\n",
    "        :type s: List[str]\n",
    "        :rtype: void Do not return anything, modify s in-place instead.\n",
    "        \"\"\"\n",
    "        x=len(s)\n",
    "        if x%2==0:\n",
    "            for i in range(x//2):\n",
    "                s[i],s[-(i+1)]=s[-(i+1)],s[i]\n",
    "        else:\n",
    "            for i in range(x//2):\n",
    "                s[i],s[-(i+1)]=s[-(i+1)],s[i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseString(self, s: 'List[str]') -> 'None':\n",
    "        \"\"\"\n",
    "        Do not return anything, modify s in-place instead.\n",
    "        \"\"\"\n",
    "        n = len(s)\n",
    "        i, j = 0, n - 1\n",
    "        while i < j:\n",
    "            s[i], s[j] = s[j], s[i]\n",
    "            i, j = i + 1, j - 1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseString(self, s):\n",
    "        \"\"\"\n",
    "        :type s: List[str]\n",
    "        :rtype: void Do not return anything, modify s in-place instead.\n",
    "        \"\"\"\n",
    "        for i in range(len(s)):\n",
    "            s.append(s[-2*i-1])\n",
    "        for i in range(int(len(s)/2)):\n",
    "            s.pop(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseString(self, s: List[str]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify s in-place instead.\n",
    "        \"\"\"\n",
    "        start, end = 0, len(s) - 1\n",
    "        print(id(s))\n",
    "        while start <= end:\n",
    "            s[start], s[end] = s[end], s[start]\n",
    "            start += 1\n",
    "            end -= 1\n",
    "        print(id(s))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseString(self, s):\n",
    "        \"\"\"\n",
    "        :type s: List[str]\n",
    "        :rtype: void Do not return anything, modify s in-place instead.\n",
    "        \"\"\"\n",
    "        end = len(s) // 2\n",
    "        r = len(s) - 1\n",
    "        for i in range(end):\n",
    "            print(i)\n",
    "            s[i], s[r-i] = s[r-i],s[i]\n",
    "        return"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseString(self, s: List[str]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify s in-place instead.\n",
    "        \"\"\"\n",
    "        return s.reverse()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseString(self, s: List[str]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify s in-place instead.\n",
    "        \"\"\"\n",
    "        s[:]=s[::-1]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseString(self, s: List[str]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify s in-place instead.\n",
    "        \"\"\"\n",
    "        j = len(s)-1\n",
    "        i = 0\n",
    "        while( i< j):\n",
    "            temp = s[i]\n",
    "            s[i] = s[j]\n",
    "            s[j] = temp\n",
    "            j -= 1\n",
    "            i += 1\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseString(self, s: List[str]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify s in-place instead.\n",
    "        \"\"\"\n",
    "        l = len(s)\n",
    "        p = 0\n",
    "        while p<l//2:\n",
    "            tmp = s[p]\n",
    "            s[p] = s[-p-1]\n",
    "            s[-p-1] = tmp\n",
    "            p+=1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseString(self, s: List[str]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify s in-place instead.\n",
    "        \"\"\"\n",
    "\n",
    "        #二分查找替换\n",
    "\n",
    "        if not s:\n",
    "            return []\n",
    "\n",
    "        left = 0\n",
    "        right = len(s) - 1 \n",
    "\n",
    "        while left < right :\n",
    "            s[left] ,s[right] = s[right],s[left]\n",
    "            left += 1\n",
    "            right -= 1 \n",
    "\n",
    "        return s         "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseString(self, s: List[str]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify s in-place instead.\n",
    "        \"\"\"\n",
    "        left,right=0,len(s)-1\n",
    "        while(left<right):\n",
    "            tmp=s[left]\n",
    "            s[left]=s[right]\n",
    "            s[right]=tmp\n",
    "            left+=1\n",
    "            right-=1\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseString(self, s: List[str]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify s in-place instead.\n",
    "        \"\"\"\n",
    "        s[:] = s[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\r\n",
    "#     def reverseString(self, s: List[str]) -> None:\r\n",
    "#         \"\"\"\r\n",
    "#         Do not return anything, modify s in-place instead.\r\n",
    "#         \"\"\"\r\n",
    "#         left, right = 0, len(s) - 1\r\n",
    "#         while(left < right):\r\n",
    "#             s[left], s[right] = s[right], s[left]\r\n",
    "#             left += 1\r\n",
    "#             right -= 1\r\n",
    "\r\n",
    "# s[::-1]表示反转s中的元素\r\n",
    "# s[:]表示数组中所有子模块\r\n",
    "# s[:]=s[::-1]表示将原数组反转后赋值给s中每一个对应的位置\r\n",
    "# s=s[::-1]表示将s反转后赋值给新的对象s（可以通过id函数查看内存地址），与题意原地修改不符。\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def reverseString(self, s: List[str]) -> None:\r\n",
    "        s[:] = s[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseString(self, s: List[str]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify s in-place instead.\n",
    "        \"\"\"\n",
    "        a = s[:]\n",
    "        s[:] = a[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseString(self, s: List[str]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify s in-place instead.\n",
    "        \"\"\"\n",
    "        new_list = [i for i in range(len(s))]\n",
    "        for k, v in enumerate(s):\n",
    "            new_list[-(k+1)] = v\n",
    "        for k, v in enumerate(new_list):\n",
    "            s[k] = v\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseString(self, s: List[str]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify s in-place instead.\n",
    "        \"\"\"\n",
    "        for i in range(len(s)//2):\n",
    "            temp = s[len(s) - i - 1]\n",
    "            s[len(s) - i - 1] = s[i]\n",
    "            s[i] = temp\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseString(self, s: List[str]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify s in-place instead.\n",
    "        \"\"\"\n",
    "        # start = 0\n",
    "        # end = len(s)-1 if len(s) != 0 else 0\n",
    "        # while start < end:\n",
    "        #     s[start], s[end] = s[end], s[start]\n",
    "        #     start += 1\n",
    "        #     end -= 1\n",
    "\n",
    "        n = list(range(len(s)))\n",
    "\n",
    "        for i,j in zip(n,n[::-1]):\n",
    "            if i >= j:\n",
    "                break\n",
    "            s[i], s[j] = s[j], s[i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseString(self, s: List[str]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify s in-place instead.\n",
    "        \"\"\"\n",
    "        i = 0\n",
    "        j = len(s)-1\n",
    "        while i<j:\n",
    "            s[i],s[j] = s[j],s[i]\n",
    "            i = i+1\n",
    "            j = j-1\n",
    "        return list(str(s))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseString(self, s: List[str]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify s in-place instead.\n",
    "        \"\"\"\n",
    "        j=len(s)-1\n",
    "        i=0\n",
    "        while i<(len(s))//2:\n",
    "            b=s[j]\n",
    "            s[j]=s[i]\n",
    "            s[i]=b\n",
    "            j=j-1\n",
    "            i=i+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseString(self, s: List[str]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify s in-place instead.\n",
    "        \"\"\"\n",
    "        left, right = 0, len(s) - 1\n",
    "        while left < right:\n",
    "            s[left], s[right] = s[right], s[left]\n",
    "            left, right = left + 1, right - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseString(self, s: List[str]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify s in-place instead.\n",
    "        \"\"\"\n",
    "        # 前序递归对应的非递归方法：递归，无回溯\n",
    "        # i = 0\n",
    "        # j = len(s)-1\n",
    "        # while i<j:\n",
    "        #     s[i],s[j] = s[j],s[i]\n",
    "        #     i = i+1\n",
    "        #     j = j-1\n",
    "        \n",
    "        # 后序递归对应的非递归方法：先递归再回溯\n",
    "        stack = []\n",
    "        i = 0\n",
    "        j = len(s)-1\n",
    "        while i<j:\n",
    "            stack.append((i,j))\n",
    "            i = i+1\n",
    "            j = j-1\n",
    "        for x,y in stack[::-1]:\n",
    "            s[x],s[y] = s[y],s[x]\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseString(self, s: List[str]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify s in-place instead.\n",
    "        \"\"\"\n",
    "        i, j = 0,len(s)-1\n",
    "        while i <= j:\n",
    "            s[i],s[j] = s[j],s[i]\n",
    "            i += 1\n",
    "            j -= 1\n",
    "        s = [si.lower() for si in s]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseString(self, s: List[str]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify s in-place instead.\n",
    "        \"\"\"\n",
    "        m=len(s)\n",
    "        i=m-1\n",
    "        while i>=0:\n",
    "            s.append(s[i])\n",
    "            s[i]=[]\n",
    "            i-=1\n",
    "        s[0:m]=[]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseString(self, s: List[str]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify s in-place instead.\n",
    "        \"\"\"\n",
    "        for i in range(len(s)):\n",
    "            tmp = s.pop()\n",
    "            print(tmp)\n",
    "            s.insert(i, tmp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def reverseString(self, s):\n",
    "        lst = list(s)\n",
    "        l, r = 0, len(lst) - 1\n",
    "\n",
    "        while l < r:\n",
    "            lst[l], lst[r] = lst[r], lst[l]\n",
    "            l += 1\n",
    "            r -= 1\n",
    "        s[:] = ''.join(lst)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseString(self, s: List[str]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify s in-place instead.\n",
    "        \"\"\"\n",
    "        left = 0\n",
    "        right = len(s)-1\n",
    "        while left < right :\n",
    "            s[left],s[right]=s[right],s[left]\n",
    "            left+=1\n",
    "            right-=1\n",
    "        return"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseString(self, s: List[str]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify s in-place instead.\n",
    "        \"\"\"\n",
    "        l, r = 0, len(s)-1\n",
    "        while l < r:\n",
    "            # 交换\n",
    "            s[l], s[r] = s[r], s[l]\n",
    "            l += 1\n",
    "            r -= 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseString(self, s: List[str]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify s in-place instead.\n",
    "        \"\"\"   \n",
    "        l, r = 0, len(s) - 1\n",
    "        while l < r:\n",
    "            s[l], s[r] = s[r], s[l]\n",
    "            l += 1\n",
    "            r -= 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseString(self, s: List[str]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify s in-place instead.\n",
    "        \"\"\"\n",
    "        left, right = 0, len(s) - 1\n",
    "\n",
    "        while left < right:\n",
    "            s[left], s[right] = s[right], s[left]\n",
    "            left += 1\n",
    "            right -= 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseString(self, s: List[str]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify s in-place instead.\n",
    "        \"\"\"\n",
    "        n=len(s)\n",
    "        l,r=0,n-1\n",
    "        while l<=r:\n",
    "            a=ord(s[l])\n",
    "            b=ord(s[r])\n",
    "            s[l]=chr(b)\n",
    "            s[r]=chr(a)\n",
    "            l+=1\n",
    "            r-=1\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseString(self, s: List[str]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify s in-place instead.\n",
    "        \"\"\"\n",
    "        n = len(s)\n",
    "        left, right = 0, n-1\n",
    "        while left < right:\n",
    "            s[left], s[right] = s[right], s[left]\n",
    "            left += 1\n",
    "            right -= 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseString(self, s: List[str]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify s in-place instead.\n",
    "        \"\"\"\n",
    "        left, right = 0, len(s) - 1\n",
    "        while left < right:\n",
    "            s[left], s[right] = s[right], s[left]\n",
    "            left += 1\n",
    "            right -= 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseString(self, s: List[str]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify s in-place instead.\n",
    "        \"\"\"\n",
    "        #temp = [i for i in s[::-1]]\n",
    "        for i in range(len(s) // 2):\n",
    "            s[i], s[len(s) - i-1] = s[len(s) - i-1], s[i]\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseString(self, s: List[str]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify s in-place instead.\n",
    "        \"\"\"\n",
    "        a = \"\"\n",
    "        for i in range(len(s)):\n",
    "            a += s[i]\n",
    "        a = a[::-1]\n",
    "        s.clear()\n",
    "        for i in range(len(a)):\n",
    "            s.append(a[i])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseString(self, s: List[str]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify s in-place instead.\n",
    "        \"\"\"\n",
    "        left, right = 0, len(s)-1\n",
    "        while left<right:\n",
    "            s[left],s[right] = s[right],s[left]\n",
    "            left += 1\n",
    "            right -= 1\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseString(self, s: List[str]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify s in-place instead.\n",
    "        \"\"\"\n",
    "        # 双指针，推荐\n",
    "        left, right = 0, len(s)-1\n",
    "        while left<right:\n",
    "            s[left],s[right] = s[right],s[left]\n",
    "            left += 1\n",
    "            right -= 1\n",
    "        return s\n",
    "        # 栈\n",
    "        stack = []\n",
    "        for char in s:\n",
    "            stack.append(char)\n",
    "        for i in range(len(s)):\n",
    "            s[i] = stack.pop()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseString(self, s: List[str]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify s in-place instead.\n",
    "        \"\"\"\n",
    "        s[:] = s[::-1]"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
